1. Field of the Invention
The present invention generally relates to resource allocation of discrete activities by data processing systems and, more particularly, to techniques for determining and applying an irredundant set of cardinality constraints enabling both interactive decision support systems and more efficient solution of related discrete optimization problems. The resource allocation may be, for example, capital, inventory, manpower, raw material, machine time, tools, and the like.
2. Description of the Prior Art
Project Management, as a modern management tool, has its origins in the early part of this century when Henry L. Gantt, while working for the government during World War I, developed his now famous visual aid for work control. The Gantt chart is a graphic representation of a project schedule that shows each task as a bar having a length proportional to the duration of the task. Later during the 1950s, Dr. John Presper Mauchley, a coinventor of the EDVAC at the University of Pennsylvania, developed the Critical Path Method (CPM) which was further developed by Willard Frazer, a consultant on the Polaris submarine project. Frazer's contribution was called Program Evaluation and Review Technique (PERT). A PERT chart is one that resembles a flow chart showing predecessor and successor tasks of a project and the critical path.
In an increasingly competitive world market, the problem of allocating available resources to, for example, manufacturing activities so as to minimize the cost of production and maximize profits is one that is the focus of considerable attention. The problem does not admit of simple solutions since there are typically many variables and often many potential solutions, a number of which may appear a priori to be equally viable. Project management techniques, however, assume that decisions have been made regarding resource allocation. For those industries where there is surplus capacity, the decisions involved in resource allocation are relatively easy, but surplus capacity is a rare commodity in today's market driven economies.
A more recent development is Materials Requirements Planning (MRP) which is a system for translating demand for final products into raw material requirements. Many authors have published papers and books in the field of production management. For example, Joseph Orlicky wrote Material Requirements Planning, published by McGraw-Hill, which has become an industry standard reference for planning requirements. MRP is essentially an information system (bill of material database, inventory database) and a simulation tool that generates proposals for production schedules which managers can evaluate in terms of their feasibility and cost effectiveness. MRP does not deal with optimization issues or with constrained resources or with discrete activities (e.g., large item production orders). An example of an MRP system is IBM's computer program product COPICS, which is currently in use in many manufacturing facilities.
MRP is an excellent planning tool. A manufacturing manager can plan purchases and production to meet forecasted final demands. However, MRP is not particularly useful for making decisions regarding the execution of the actual manufacturing process. This is particularly true when demand forecasts are inexact and raw material lead time is long. In these circumstances, the manufacturing manager or production controller is often faced with raw material inventory that is inadequate to meet all of planned or committed short-term demand. Decision support tools are needed to aid the manager in determining and evaluating possible production plans. If the demand corresponds to specific customer orders, and partial orders are of no value to the customer, as in the case of aircraft, heavy machinery, large mainframe computers, and the like, then determining producing plans is equivalent to selecting a set of orders to complete.
Generalizing, the twin goals of minimizing cost and maximizing profits may be characterized as maximizing benefit. Since no benefit is obtained unless an activity is completed, there is no advantage to allocating resources to activities which are only partially completed. Thus, an activity is either to be completed, or it is not to be allocated any resource. This is equivalent to selecting a set of activities to undertake, providing that there is sufficient resource to complete all the undertaken activities, and among all such sets, selecting the set that has the greatest total benefit. Since each activity is either to be completed, or not undertaken, the decision variables associated with their activities are discrete; that is, each takes either the value 0 (meaning activity is not undertaken) or the value 1 (meaning that the activity is completed). The optimization problem to be solved is one of discrete activity resource allocation (DARA).
The discrete activity resource allocation problem has many important applications, particularly, but not exclusively, in manufacturing planning and management. Some representative applications include the following:
1. Product families allocation to worldwide plants. PA1 2. Sourcing decisions on long-term production planning. PA1 3. Inter-plant aggregate production planning. PA1 4. Vendor production allocation to final products. PA1 5. Components allocation to final products in a multi-product, multi-period, single-level environment. PA1 6. Components allocation to subassemblies and final products in a multi-product, multi-period, multi-level environment. PA1 7. Capacity expansion planning. PA1 8. Workload allocation to machines, tools, operators on a short-term environment. PA1 9. Operation execution sequencing. PA1 10. Material flow allocation. PA1 11. Parts input sequencing and scheduling on a manufacturing floor. PA1 12. Parts routing planning. PA1 13. Operation execution scheduling. PA1 14. Parts transportation scheduling. PA1 A vendor is chosen for the supply of a given raw material. PA1 A plant, department, shift, process is chosen for the production of a given subassembly or final product. PA1 A product is assigned to a given machine at a given period. PA1 A change of jobs or part types assembly is scheduled in a given machine at a given period and, then, some setup is required. PA1 A given Bill of Materials is chosen for the assembly of a product at a given period. PA1 .delta..sub.2 .delta..sub.1 +.delta..sub.6 .ltoreq.1--which means choose at most one of the activities 2 and 6; PA1 .delta..sub.3 +.delta..sub.6 .ltoreq.1--which means choose at most one of the activities 3 and 6; PA1 .delta..sub.2 +.delta..sub.3 +.delta..sub.4 +.delta..sub.5 +.delta..sub.6 .ltoreq.2--which means choose at most two of the activities 2, 3, 4, 5, and 6.
The resources can be so diverse as in-house producing units (i.e., plants), selected sets of outside sources (i.e., third parties or vendors), information devices and raw materials inventory as well as (physical) manufacturing resources such as machine time available, manpower hours, tools, robots, ovens, testers, warehouse, energy, transportation units and raw materials. The activities can be production to be allocated to different plants, geographical sectors or countries, in total or per period, on the planning horizon as well as on subassemblies to be produced at given periods, jobs or orders that are to be released to the manufacturing floor at given shifts, and so on.
There is another activity that consists of the existence of the allocation of a given resource to a given activity. Examples of what is called the do event are as follows:
Because of the importance of the problem of discrete activity resource allocation, efforts have been made to characterize the problem mathematically so as to better analyze the problem and arrive at a solution. For example, the DARA problem may be mathematically characterized as follows. Let I be a set of resource and for each i.epsilon.I, let b.sub.i denote the available quantity of resource i. Let J be a set of activities and for each j.epsilon.J, let c.sub.j denote the benefit obtained from completion of activity j. No benefit is received for incomplete activities. It is assumed that each activity, if it is to be undertaken, will be completed and will consume some available resource(s). It is also assumed that the quantity of resource required by an activity is completely determined by the resource and the activity and is not influenced by the combination of activities undertaken. For each resource-activity pair i,j, with i.epsilon.I and j.epsilon.J, the quantity a.sub.ij .gtoreq.0 is defined as the quantity of resource i required to complete activity j. It is assumed that activities do not produce resources, other than the associated benefit. That is, a.sub.ij .gtoreq.0 for all i.epsilon.I and j.epsilon.J.
Let the decision regarding activity i be denoted by the variable .delta..sub.i, where .delta..sub.i =1 means that the activity i is completed and .delta..sub.i =0 means that the activity i is not undertaken. Then the discrete activity resource allocation problem can be written as a 0-1 integer program (IP) ##EQU1## where .delta. is a column vector of the 0-1 variables, c is the benefit vector, A is the coefficient matrix of the constraint (representing resource requirements by the activities), and b is the vector of resource availabilities. All vectors and the matrix are assumed to have the appropriate dimensions.
The most common method for solving the mixed 0-1 program (1.1) above consists of relaxing the integrality requirement of the vector .delta., replacing it with the bounding constraint 0.ltoreq..delta..ltoreq.1, solving the associated linear program (LP) and then using a branch-and-bound methodology to obtain a solution that satisfies the integrality constraint. This is described, for example, by K. Hoffman and M. Padberg, "LP-based combinatorial problem solving", Annals of Operations Research 4 (1985), pp. 145-194, and by G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, J. Wiley, N.Y. (1988). The branch-and-bound phase of such a procedure can require examination of an exponential number of nodes, and examining each node typically requires solving a LP that starts from a dual feasible, primal near-feasible solution.
Pre-processing techniques that fix some of the binary variables to their optimal values before solving the LP can reduce the number of nodes requiring examination. See, for example, M. Guignard and K. Spielberg, "Logical Reduction Methods in Zero-One Programming (Minimal Preferred Variables)", Operations Research 29 (1981), pp. 49-74, and U. H. Suhl, "Solving large-scale mixed-integer programs with fixed charge variables", Mathematical Programming 32 (1985), pp. 165-182. Reformulating the problem (1.1), so that the same vectors having integer .delta. are feasible but the optimal LP value is increased, can also significantly reduce the number of subproblems to be solved. Some techniques for problem reformulation can be found in Crowder, E. L. Johnson and M. Padberg, "Solving large-scale zero-one linear programming problems", Operations Research 31 (1983), pp. 803-834, T. Van Roy and L. A. Wolsey, "Solving mixed integer programming problems using automatic reformulation", Operations Research 35 (1987), pp. 45-57, and H. P. Williams, Model Building in Mathematical Programming, J. Wiley N.Y. (1978), as well as the article by M. Guignard et al. and the text book by G. L. Nemhouser et al. cited above, and research in this area continues, mainly, in the direction of reformulating the subproblems encountered in the branch-and-bound procedure. The LP relaxation of the problem (1.1) can be strengthened by adding additional linear constraints (called cutting planes) that eliminate only vectors satisfying the problem (1.1) but having non-integer .delta.. See, for example, V. Chvatal, "Edmonds polytopes and a hierarchy of combinatorial problems", Discrete Mathematics 4 (1973), pp. 305-357, and R. E. Gomory, "Outline an algorithm for integer solutions to linear programs", Bulletin of the American Mathematical Society 64 (1958), pp. 275-278. An overall framework for this type of methodology is described in the article by M. Guignard et al. above. See also the article by H. Crowder et al. cited above and L. F. Escudero, "S3 sets. An extension of the Beale-Tomlin special ordered sets", Mathematical Programming 42 (1988), pp. 113-123.